package com.darrenchan.leetcode;

/**
 * @Desc
 * @Author chenchi03
 * @CreateTime 2020-01-26 18:03
 */
public class Q5 {
    public String longestPalindrome(String ss) {
        if(ss == null || ss.length() == 0){
            return ss;
        }

        char[] s = ss.toCharArray();
        boolean[][] isPalin = calcPalin(s);
        int len = s.length;

        int max = 1, start = 0;
        for (int j = 1; j < len; j++) {
            for (int i = 0; i < j; i++) {
                if(isPalin[i][j] && max < j - i + 1){
                    max = j - i + 1;
                    start = i;
                }
            }
        }

        return ss.substring(start, start + max);
    }

    private boolean[][] calcPalin(char[] s) {
        int n = s.length;
        boolean[][] isPalin = new boolean[n][n];

        int i, j, c;
        for (c = 0; c < n; c++) {
            i = j = c;
            while (i >= 0 && j < n && s[i] == s[j]){
                isPalin[i][j] = true;
                i--;
                j++;
            }
        }

        for (c = 0; c < n - 1; c++) {
            i = c;
            j = c + 1;
            while (i >= 0 && j < n && s[i] == s[j]){
                isPalin[i][j] = true;
                i--;
                j++;
            }
        }

        return isPalin;
    }


    public String longestPalindrome2(String ss) {
        if(ss == null || ss.length() == 0){
            return ss;
        }

        char[] s = ss.toCharArray();
        int len = s.length;

        int max = 1, start = 0;
        int i, j;
        for (int c = 0; c < len; c++) {
            i = j = c;
            while(i >= 0 && j < len && s[i] == s[j]) {
                if(max < j - i + 1){
                    max = j - i + 1;
                    start = i;
                }
                i--;
                j++;
            }
        }

        for (int c = 0; c < len - 1; c++) {
            i = c;
            j = c + 1;
            while(i >= 0 && j < len && s[i] == s[j]) {
                if(max < j - i + 1){
                    max = j - i + 1;
                    start = i;
                }
                i--;
                j++;
            }
        }

        return ss.substring(start, start + max);
    }
}
